import random
import time
import sys

sys.setrecursionlimit(1000000)


class sort():

    def __init__(self, n):
        """
        n是问题规模
        """
        self.len = n
        self.arr = [0] * n
        self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.arr[i] = random.randint(0,99)


    def partition(self, left, right):
        k = left
        random_pos = random.randint(left, right)
        self.arr[random_pos], self.arr[right] = self.arr[right], self.arr[random_pos]
        for i in range(left, right):
            if self.arr[i] < self.arr[right]:
                self.arr[i], self.arr[k] = self.arr[k], self.arr[i]
                k += 1
        self.arr[k], self.arr[right] = self.arr[right], self.arr[k]
        return k


    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)


    def adjust_max_heap(self, pos, arr_len):
        arr = self.arr
        parent = pos
        son = parent * 2 + 1
        while son < arr_len:
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son += 1;
            if arr[parent] < arr[son]:
                arr[parent], arr[son] = arr[son], arr[parent]
                parent = son
                son = parent * 2 + 1
            else:
                break

    def heap_sort(self):
        arr = self.arr
        # 调整为大根堆
        for i in range(self.len//2 - 1, -1, -1):
            self.adjust_max_heap(i, self.len)
        arr[0], arr[self.len-1] = arr[self.len-1], arr[0]
        for i in range(self.len-1, 1, -1):
            self.adjust_max_heap(0, i)
            arr[0], arr[i - 1] = self.arr[i - 1], arr[0]

    def time_use_func(self, sort_func, *args, **kwargs):
        start = time.time()
        sort_func(*args, **kwargs)
        end = time.time()
        print(f'Time taken: {end - start}')



if __name__ == '__main__':

    count = 100000
    my_sort = sort(count)
    # my_sort.quick_sort(0, count - 1)
    # my_sort.heap_sort()
    my_sort.time_use_func(my_sort.quick_sort, 0, count - 1)